package java学习.leetcode.editor.cn;

import java.util.*;

/**
 * @author 刘世锦
 * 2022-11-12 18:07:03	 当前时间
 */
//给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位
//。 
//
// 返回 滑动窗口中的最大值 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
//输出：[3,3,5,5,6,7]
//解释：
//滑动窗口的位置                最大值
// 0  1  2  3  4  5  6  7  8  9
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3 | 1 3
// 1 [3  -1  -3] 5  3  6  7       3 | 3
// 1  3 [-1  -3  5] 3  6  7       5 | -1 5
// 1  3  -1 [-3  5  3] 6  7       5 | -3 5
// 1  3  -1  -3 [5  3  6] 7       6 |  5 6
// 1  3  -1  -3  5 [3  6  7]      7 |  3 6 7
// 
//
// 示例 2： 
//
// 
//输入：nums = [1], k = 1
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 105 
// -104 <= nums[i] <= 104 
// 1 <= k <= nums.length 
// 
// Related Topics 队列 数组 滑动窗口 单调队列 堆（优先队列） 
// 👍 1974 👎 0

public class 滑动窗口最大值{
	public static void main(String[] args) {
		Solution solution = new 滑动窗口最大值().new Solution();
		int[] nums =  {1,3,-1,-3,5,3,6,7};int k = 3;
//		int[] nums =  {1,-1};int k = 1;

		solution.maxSlidingWindow(nums,k);
	}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

	// 定义单调队列：队列中的元素都是单调递增/递减的。且队首元素为Max/Min
class Myqueue{// 单调递减
	Deque<Integer> queue ;

	public Myqueue() {
		queue = new ArrayDeque<>();
	}
//	添加一个元素
	public void offer(int val){
//		若 当前元素比现在的队列队尾大，则破坏了单调递减，全部poll清除
		while (!queue.isEmpty()&& queue.getLast()<val){
			queue.removeLast();
		}
//		加入新元素
		queue.offer(val);
	}

/**
 * 当前要删的元素正是队首(Max),则删除元素
 * 其余情况在push之前就已poll
 */
	public void poll(int val){
		if (!queue.isEmpty()&&queue.getFirst()==val){
			queue.poll();
		}
	}

/**
 * 	单调栈  队首即Max
 */
	public int getMaxValue(){
		return queue.peek();
	}

}


	/**
	 * 1. 确定窗口的右边界。
	 *
	 *
	 */
// 0  1  2  3  4  5  6  7  8  9
//---------------               -----
//[1  3  -1] -3  5  3  6  7       3 | 1 3
// 1 [3  -1  -3] 5  3  6  7       3 | 3
// 1  3 [-1  -3  5] 3  6  7       5 | -1 5
// 1  3  -1 [-3  5  3] 6  7       5 | -3 5
// 1  3  -1  -3 [5  3  6] 7       6 |  5 6
// 1  3  -1  -3  5 [3  6  7]      7 |  3 6 7
	public int[] maxSlidingWindow2(int[] nums, int k) {
//		队列存放的是 数组的下标，因为移动窗口需要比较，随后poll元素
		ArrayDeque<Integer> deque = new ArrayDeque<>();
		int index = 0;
		int len = nums.length-k+1;
		int[]dp = new int[len];
		for (int right = 0; right < nums.length; right++) {
			// 清除元素，保证队首是Max
			while (!deque.isEmpty()&&nums[deque.getLast()]<nums[right]){
				deque.removeLast();
			}
			// 添加数组下标
			deque.offerLast(right);
			int left = right-k+1;
			// 此时窗口要前移,需要将队头出队
			if (!deque.isEmpty()&&deque.peek()<left){
				deque.poll();
			}
			//  只有队列的个数>=k后，才会构成题意的队列
			if (right>=k-1){
				dp[index++] = nums[deque.peek()];
			}
//			System.out.println(deque);
		}
		System.out.println(Arrays.toString(dp));

		return dp;

	}

	public int[] maxSlidingWindow(int[] nums, int k) {
//		int i = 0,j = k-1;
		int len = nums.length-k+1;
		int[]dp = new int[len];
		Myqueue myqueue = new Myqueue();
		for (int i = 0; i <k ; i++) {
			myqueue.offer(nums[i]);
		}
		int num = 0;
		dp[num++] = myqueue.getMaxValue();
//		for (int i = k; i < nums.length; i++) {
//			myqueue.poll(nums[i-k]);
//			myqueue.offer(nums[i]);
//			int maxValue = myqueue.getMaxValue();
//			dp[num++] = maxValue;
//		}
		for (int i = 0; i < nums.length-k; i++) {
			myqueue.poll(nums[i]);
			myqueue.offer(nums[i+k]);
			int maxValue = myqueue.getMaxValue();
			dp[num++] = maxValue;
		}
		System.out.println(Arrays.toString(dp));
		return dp;
	}
    public int[] maxSlidingWindowTime_Limit_Exceeded(int[] nums, int k) {
//		int i = 0,j = k-1;
		int len = nums.length-k+1;
		int[]dp = new int[len];
		for (int i = 0; i < len; i++) {
			int j = i,max = nums[i];
			while (j-i<k){
				max = Math.max(max,nums[j]);
				j++;
			}
			dp[i] = max;
		}
//		System.out.println(Arrays.toString(dp));
		return dp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
